Wannfly挑战赛19 B 矩阵

给一个$R·C$的矩阵,问满足以下三个条件的最大子矩阵。
子矩阵不超过 $X$ 行。
子矩阵不超过 $Y$ 列。
子矩阵中 $0$ 的个数不能超过 $Z$ 个。
$(R,C,X,Y\le500,Z\le R·C)$


题解

  • 枚举符合条件的两行
  • 用剩下两个条件单调队列 列的范围
  • 时间复杂度 $O(R·C^2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,m,c[505][505],X,Y,Z, a[505][505], lin[505][505], nowc[505], nowlin[505];
ll ans;

int main()
{
scanf("%lld%lld%lld%lld%lld", &n,&m,&X,&Y,&Z);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++){
scanf("%lld", &a[i][j]);
c[i][j]=c[i-1][j]+a[i][j];
lin[i][j]=lin[i-1][j]+(a[i][j]==0);
}
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n&&(j-i+1)<=X;j++)
{
for(int k=1;k<=m;k++)
{
nowc[k]=c[j][k]-c[i-1][k]+nowc[k-1];
nowlin[k]=lin[j][k]-lin[i-1][k]+nowlin[k-1];
}
deque<pair<ll,int>>q;
q.push_back({0, 0});
for(int l=1,r=1;r<=m;r++)
{
while(r-l+1>Y || nowlin[r]-nowlin[l-1]>Z) l++;
while(!q.empty() && q.back().first>nowc[r]) q.pop_back();
while(!q.empty() && q.front().second<l-1)q.pop_front();
q.push_back({nowc[r], r});
ans=max(ans, nowc[r]-q.front().first);
}
}
}
printf("%lld\n", ans);
}